#ifndef GRAPH_H
#define GRAPH_H
#include "inc/main_color.h"
#include "dist_calculator.h"
#include "elements.h"
#include <vector>
#include <string>
#include "assert.h"

class IGraph
{
public:
    virtual size_t numVertecies() const = 0;
    virtual bool isConnected(size_t u, size_t v) const = 0;
    virtual const std::vector<size_t>& incendents(size_t u) const = 0;
    virtual size_t degree(size_t u) const
    {
        return incendents(u).size();
    }
    virtual size_t vertex(size_t u) const = 0;
    virtual std::string name() const = 0;

};

class FullGraph: public IGraph
{
public:
    FullGraph(size_t minDist, size_t maxDist)
        :minDist_(minDist), maxDist_(maxDist)
    {
        for(size_t u = 0; u < NUM_VERTICES; ++u) {
            for(size_t v = 0; v < NUM_VERTICES; ++v) {
                if (isConnected(u, v)) {
                    incendents_[u].push_back(v);
                }
            }
        }
    }

    bool isConnected(size_t u, size_t v) const
    {
        size_t d = distanceCalculator(vertex(u), vertex(v));
        return minDist_ <= d && d <= maxDist_;
    }

    const std::vector<size_t>& incendents(size_t u) const
    {
        return incendents_[u];
    }

    size_t numVertecies() const
    {
        return NUM_VERTICES;
    }

    size_t vertex(size_t u) const
    {
        return elements[u];
    }

    std::string name() const
    {
        char res[100];
        sprintf(res, "full_graph_%d_%d", (int)minDist_, (int)maxDist_);
        return res;                                          
    }

private:
    size_t minDist_, maxDist_;
    std::vector<size_t> incendents_[NUM_VERTICES];
};

class FullParityGraph: public IGraph
{
public:
    FullParityGraph(size_t minDist, size_t maxDist, size_t parity,
            std::vector<size_t> limitters = std::vector<size_t>())
        :minDist_(minDist), maxDist_(maxDist), parity_(parity), limitters_(limitters)
    {
        for(size_t u = 0; u < NUM_VERTICES; ++u) {
            for(size_t v = 0; v < NUM_VERTICES; ++v) {
                if (isConnected(u, v)) {
                    incendents_[u].push_back(v);
                }
            }
        }
    }

    bool isConnected(size_t u, size_t v) const
    {
        if (distanceCalculator(0, vertex(u)) % 2 != parity_
            || distanceCalculator(0, vertex(v)) % 2 != parity_) {
            return false;
        }
        bool gu, gv;
        gu = gv = limitters_.empty();
        for (size_t i = 0; i < limitters_.size(); ++i) {
            size_t limitter = limitters_[i];
            gu |= u >= limitter;
            gv |= v >= limitter;
            if (distanceCalculator(vertex(limitter), vertex(u)) > maxDist_ || 
                distanceCalculator(vertex(limitter), vertex(v)) > maxDist_) {
                return false;
            }
        }
        if (!gu || !gv) {
            return false;
        }
        size_t d = distanceCalculator(vertex(u), vertex(v));
        return minDist_ <= d && d <= maxDist_;
    }

    const std::vector<size_t>& incendents(size_t u) const
    {
        return incendents_[u];
    }

    size_t numVertecies() const
    {
        return NUM_VERTICES;
    }

    size_t vertex(size_t u) const
    {
        return elements[u];
    }

    std::string name() const
    {
        char res[100];
        sprintf(res, "full_parity_%d_graph_%d_%d", (int)parity_, 
                (int)minDist_, (int)maxDist_);
        return res;                                          
    }

private:
    size_t minDist_, maxDist_, parity_;
    std::vector<size_t> limitters_;
    std::vector<size_t> incendents_[NUM_VERTICES];
};

class Graph: public IGraph
{
public:
    Graph(size_t minDist, size_t maxDist, const std::vector<size_t>& vertecies)
        :minDist_(minDist), maxDist_(maxDist), vertecies_(vertecies)
    {
        for(size_t u = 0; u < vertecies.size(); ++u) {
            for(size_t v = 0; v < vertecies.size(); ++v) {
                if (isConnected(u, v)) {
                    incendents_[u].push_back(v);
                }
            }
        }
    }

    bool isConnected(size_t u, size_t v) const
    {
        size_t d = distanceCalculator(vertex(u), vertex(v));
        return minDist_ <= d && d <= maxDist_;
    }

    const std::vector<size_t>& incendents(size_t u) const
    {
        return incendents_[u];
    }

    size_t numVertecies() const
    {
        return vertecies_.size();
    }

    size_t vertex(size_t u) const
    {
        return elements[vertecies_[u]];
    }

    std::string name() const
    {
        char res[100];
        sprintf(res, "graph_%d_%d", (int)minDist_, (int)maxDist_);
        return res;                                          
    }

private:
    size_t minDist_, maxDist_;
    std::vector<size_t> vertecies_;
    std::vector<size_t> incendents_[NUM_VERTICES];
};

class IgnoreGraph: public IGraph
{
public:
    IgnoreGraph(const IGraph* const graph, const std::vector<size_t>& vertecies)
        :graph_(graph), vertecies_(vertecies)
    {
        for(size_t u = 0; u < graph_->numVertecies(); ++u) {
            for(size_t v = 0; v < graph_->numVertecies(); ++v) {
                if (isConnected(u, v)) {
                    incendents_[u].push_back(v);
                }
            }
        }
    }

    bool isConnected(size_t u, size_t v) const
    {
        if (!binary_search(vertecies_.begin(), vertecies_.end(), u) ||
            !binary_search(vertecies_.begin(), vertecies_.end(), v)) {
            return false;
        }
        return graph_->isConnected(u, v);
    }

    const std::vector<size_t>& incendents(size_t u) const
    {
        return incendents_[u];
    }

    size_t numVertecies() const
    {
        return graph_->numVertecies();
    }

    size_t vertex(size_t u) const
    {
        return graph_->vertex(u);
    }

    std::string name() const
    {
        return "ignore_graph_of_" + graph_->name();
    }

private:
    const IGraph* const graph_;
    std::vector<size_t> vertecies_;
    std::vector<size_t> incendents_[NUM_VERTICES];

};

class SubGraph: public IGraph
{
public:
    SubGraph(const IGraph* const graph, const std::vector<size_t>& vertecies)
        :graph_(graph), vertecies_(vertecies)
    {
        for(size_t u = 0; u < vertecies.size(); ++u) {
            for(size_t v = 0; v < vertecies.size(); ++v) {
                if (isConnected(u, v)) {
                    incendents_[u].push_back(v);
                }
            }
        }
    }

    bool isConnected(size_t u, size_t v) const
    {
        return graph_->isConnected(vertecies_[u], vertecies_[v]);
    }

    const std::vector<size_t>& incendents(size_t u) const
    {
        return incendents_[u];
    }

    size_t numVertecies() const
    {
        return vertecies_.size();
    }

    size_t vertex(size_t u) const
    {
        return graph_->vertex(vertecies_[u]);
    }

    std::string name() const
    {
        return "sub_graph_of_" + graph_->name();
    }

private:
    const IGraph* const graph_;
    std::vector<size_t> vertecies_;
    std::vector<size_t> incendents_[NUM_VERTICES];

};

class CommonGraph: public IGraph
{
public:
    CommonGraph(size_t numVertecies)
        :numVertecies_(numVertecies)
    {
    }

    bool isConnected(size_t u, size_t v) const
    {
        return std::find(incendents_[u].begin(), incendents_[u].end(), v)
            != incendents_[u].end();
    }

    const std::vector<size_t>& incendents(size_t u) const
    {
        return incendents_[u];
    }

    size_t numVertecies() const
    {
        return numVertecies_;
    }

    size_t vertex(size_t u) const
    {
        return u;
    }

    void addEdge(size_t u, size_t v)
    {
        assert(u < numVertecies_);
        assert(v < numVertecies_);
        incendents_[u].push_back(v);
        incendents_[v].push_back(u);
    }

    std::string name() const
    {
        char res[100];
        sprintf(res, "common_graph_%zu", numVertecies_);
        return res;
    }

private:
    size_t numVertecies_;
    std::vector<size_t> incendents_[NUM_VERTICES];

};

size_t naiveColoring(const IGraph* const graph);
size_t runningNaiveColoring(const IGraph* const graph);

bool correctColoring(const IGraph* const graph);

bool biparate(const IGraph* const graph);

void draw(const IGraph* const graph, std::ostream& out);
void draw(const IGraph* const graph, std::string fname);

void printInDIMACS(const IGraph* const graph, std::ostream& out);

GraphC *convertToGraphC(const IGraph* const graph);
#endif//GRAPH_H
